package com.s2.link;

import com.s1.array.IList;

public class LinkedList implements IList {
	
	public static class Node {
		
		public Node(){}
		
		public Node(Integer data) {this.data = data; }

		public Integer data;

		public Node next;

		@Override
		public String toString() {
			return "Node [data=" + data + "]";
		}

	}

	protected Node headNode;

	public LinkedList() {
		this(null);
	}

	public LinkedList(Node headNode) {
		this.headNode = headNode;
	}

	@Override
	public void print() {
		Node pNode = headNode;
		System.out.print("[");
		if (pNode != null) {
			System.out.print(pNode.data);
			while ((pNode = pNode.next) != null) {
				System.out.print(" -> " + pNode.data);
			}
		}
		System.out.println("]");
	}

	// 标准add，head 指针会移动
	@Override
	public void add(Integer data) {
		this.addLast(data);
	}

	@Override
	public void addFirst(Integer data) {
		this.add(0, data);
	}

	// 当链表为空 添加头结点 有特殊处理
	@Override
	public void addLast(Integer data) {
		Node newNode = new Node();
		newNode.data = data;

		Node tailNode = this.findTailNode();
		if (tailNode == null) {
			headNode = newNode;
		} else {
			// 新增节点
			tailNode.next = newNode;
		}
	}

	@Override
	public void add(int position, Integer data) {
		if (position < 0) {
			return;
		}
		// 添加头结点
		if (position == 0) {
			Node newNode = new Node(data);
			newNode.next = this.headNode;
			this.headNode = newNode;
		}
		// position 大于 0 的情况
		else {
			Node findNode = this.findByPosition(position - 1);
			if (findNode != null) {
				Node newNode = new Node(data);
				this.insertNodeAfter(findNode, newNode);
			}
		}
	}
	
	private void insertNodeAfter(Node currNode, Node newNode) {
		newNode.next = currNode.next;
		currNode.next = newNode;
	}

	@Override
	public Object remove() {
		return this.removeLast();
	}

	@Override
	public Object removeFirst() {
		return this.remove(0);
	}

	// 当链表长度为1 删除尾结点 有特殊处理
	@Override
	public Object removeLast() {
		Integer data = null;
		if (this.headNode != null) {
			if (this.headNode.next == null) {
				data = this.headNode.data;
				this.headNode = null;
				return data;
			} else {
				Node tailNode = this.findPreTailNode();
				data = tailNode.next.data;
				tailNode.next = null;
				return data;
			}
		}	
		return data;
	}

	@Override
	public Object remove(int position) {
		Integer data = null;
		if (position == 0) {
			if (this.headNode != null) {
				data = this.headNode.data;
				if (this.headNode.next == null) {
					this.headNode = null;
				} else {
					Node node = this.headNode;
					this.headNode = this.headNode.next;
					node.data = null;
					node.next = null;
				}
			}			
		} else if (position > 0) {
			Node preNode = this.findByPosition(position - 1);
			if (preNode != null) {
				data = preNode.next.data;
				preNode.next = preNode.next.next;
			}
		}
		return data;
	}
	
	@Override
	public Object remove(Object obj) {
		if (this.headNode == null) {
			return null;
		} 
		Node pre = null;
		Node cur = this.headNode;
		Integer data = null;
		
		while (cur.next != null) {
			if (cur.data.equals(obj)) {
				if (pre == null) {
					data = this.headNode.data;
					this.headNode = this.headNode.next;
				} else {
					data = pre.next.data;
					pre.next = pre.next.next;
				}
				break;
			}
			pre = cur;
			cur = cur.next;
		}
		return data;
	}

	public Node findByPosition(int position) {
		Node findNode = this.headNode;
		for (int i = 0; i < position; i++) {
			if (findNode == null) {
				return null;
			}
			findNode = findNode.next;
		}
		return findNode;
	}

	public Node findByData(Object data) {
		Node findNode = this.headNode;
		do {
			if (data.equals(findNode.data)) {
				return findNode;
			}
			findNode = findNode.next;
		} while (findNode != null);
		return null;
	}

	@Override
	public boolean updateByPosition(int position, Integer newData) {
		Node findNode = this.findByPosition(position);
		if (findNode != null) {
			findNode.data = newData;
			return true;
		}
		return false;
	}

	@Override
	public boolean updateByData(Integer oldData, Integer newData) {
		Node findNode = this.findByData(oldData);
		if (findNode != null) {
			findNode.data = newData;
			return true;
		}
		return false;
	}

	// 找到尾节点
	private Node findTailNode() {
		while (this.headNode == null) {
			return null;
		}
		Node findNode = this.headNode;
		while (findNode.next != null) {
			findNode = findNode.next;
		}
		return findNode;
	}

	// 找到尾节点的上一个节点(倒数第二个节点)
	private Node findPreTailNode() {
		if (this.headNode == null || this.headNode.next == null) {
			return null;
		}
		Node findNode = this.headNode;
		while (findNode.next.next != null) {
			findNode = findNode.next;
		}
		return findNode;
	}

	@Override
	public void clear() {
		if (this.headNode == null) {
			return;
		}
		while (this.headNode.next != null) {
			Node node = this.headNode;
			this.headNode = this.headNode.next;
			node.data = null;
			node.next = null;
		}
		this.headNode = null;
	}

	public void reverse() {
		Node pre = null;
		Node curr = this.headNode;
		Node next;
		while (curr != null) {
			next = curr.next;
			curr.next = pre;
			pre = curr;
			curr = next;
		}
		this.headNode = pre;
	}
	
	//　判断是否为回文 
    public boolean palindrome() {
    	// 根据快慢指针找到中间节点, 但是不知道总结点个数是奇还是偶数
    	if (this.headNode == null) {
			return false;
		}
    	if (this.headNode.next == null) {
			return true;
		}
    	// 大于两个节点
		Node slow = this.headNode;
		Node fast = this.headNode;
		while (fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		
		//  slow  fast
		//  1     2
		//  1     2   3
		System.out.println("slow " + slow);
		System.out.println("fast " + fast);
		
		Node leftNode;
		Node rightNode;
		// 总奇数个， 一个重点
		if (fast.next == null) {
			rightNode = slow.next;
			this.inverseLinkList(slow);
			leftNode = slow.next;
		} 
		//  总偶数个数，两个中点 
		else {
			rightNode = slow.next;
			this.inverseLinkList(slow);
			leftNode = slow;
		}        	
		return this.TFResult(leftNode, rightNode);
    }
    
    private boolean TFResult(Node leftNode, Node rightNode) {
    	Node left = leftNode;
        Node right = rightNode;
    	while (left != null) {
    		if (!left.data.equals(right.data)) {
    			return false;
    		}
    		left = left.next;
    		right = right.next;
		}
		return true;
    }

	// 表中环的检测
	public static boolean checkCircle(LinkedList list) {
		Node headNode = list.headNode;
		if (headNode == null) {
			return false;
		}
		Node slow = headNode;
		Node fast = headNode;
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;

			if (slow == fast)
				return true;
		}
		return false;
	}

	// 两个有序的链表合并
	public static LinkedList merge(LinkedList list1, LinkedList list2) {
		// 利用哨兵结点简化实现难度
		Node soldier = new Node();
		Node p = soldier;

		Node headNode1 = list1.headNode;
		Node headNode2 = list2.headNode;

		while (headNode1 != null && headNode2 != null) {
			if (headNode1.data < headNode2.data) {
				p.next = headNode1;
				headNode1 = headNode1.next;
			} else {
				p.next = headNode2;
				headNode2 = headNode2.next;
			}
			p = p.next;
		}
		if (headNode1 != null) {
			p.next = headNode1;
		}
		if (headNode2 != null) {
			p.next = headNode2;
		}
		return new LinkedList(soldier.next);
	}

	// 删除链表倒数第 k 个结点
	public static LinkedList deleteLastKth(LinkedList list, int k) {
		if (list.headNode == null || k <= 0) {
			return list;
		}
		Node fast = list.headNode;
		int i = 1;
		// 间距 k - 1
		while (i < k && fast != null) {
			fast = fast.next;	
			i++;
		}
		
		if (fast == null) {
			return list;
		}
		
		Node slow = list.headNode;
		Node pre = null;
		while (fast.next != null) {
			fast = fast.next;			
			pre = slow;
			slow = slow.next;
		}
		
		// 删除头结点
		if (pre == null) {
			list.headNode = list.headNode.next;
		} else {
			pre.next = pre.next.next;
		}
		return list;
	}

	// 求链表的中间结点
	public static Node findMiddleNode(LinkedList list) {
		if (list.headNode == null) {
			return null;
		}
		Node slow = list.headNode;
		Node fast = list.headNode;
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}
	
	public void inverseLinkList(Node p) {
		Node pre = null;
		Node curr = this.headNode;
		Node next;
		while (curr != p) {
			next = curr.next;
			curr.next = pre;
			pre = curr;
			curr = next;
		}
		curr.next = pre;
		p = curr;
	}

}
